// 使用动态规划实现最长递增子序列
// ref: 力扣300题 https://leetcode.cn/problems/longest-increasing-subsequence/description/

#include <vector>
#include <iostream>
#include <limits.h>


/**
 *! @brief  使用动态规划计算序列中的最长递增子序列的长度 
 * 
 * @param  nums   原始序列数据
 * 
 * @return int    序列中的最长递增子序列的长度 
 */
int lengthOfLIS(std::vector<int> &nums) {
    if (nums.size() == 0)  return 0;

    // 1. 第i个元素的最长递增子序列是它前面一个比它小的最长递增子序列长度+1
    std::vector<int> dp(nums.size(), 1);
    for (int i = 1; i < dp.size(); i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {    
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    // 2. 再遍历一次，找出最长的
    int res = 1;       
    for (int i = 1; i < dp.size(); i++) {
        if (dp[i] > res) res = dp[i];
    }
    return res;
}


int main(int argc, char* argv[]) {
    std::vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18, 500}; // {2,3,7,18,500} 
    std::cout << lengthOfLIS(nums) << std::endl;

    return 0;
}